//class Solution {
//public:
//    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
//        _hanota(A, B, C, A.size());
//    }
//
//    void _hanota(vector<int>& A, vector<int>& B, vector<int>& C, int num)
//    {
//        if (num == 0) return;
//        if (num == 1)
//        {
//            C.push_back(A.back());
//            A.pop_back();
//            return;
//        }
//
//
//        _hanota(A, C, B, num - 1);
//        C.push_back(A.back());
//        A.pop_back();
//        _hanota(B, A, C, num - 1);
//    }
//};




//class Solution {
//public:
//    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//        if (n == 0) return;
//        if (m == 0)
//        {
//            for (int i = 0; i < n; i++)
//                nums1[i] = nums2[i];
//            return;
//        }
//
//        if (nums1[m - 1] > nums2[n - 1])
//        {
//            nums1[m + n - 1] = nums1[m - 1];
//            merge(nums1, m - 1, nums2, n);
//        }
//        else
//        {
//            nums1[m + n - 1] = nums2[n - 1];
//            merge(nums1, m, nums2, n - 1);
//        }
//    }
//};




//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//        if (list1 == nullptr) return list2;
//        if (list2 == nullptr) return list1;
//        if (list1->val < list2->val)
//        {
//            list1->next = mergeTwoLists(list1->next, list2);
//            return list1;
//        }
//        else
//        {
//            list2->next = mergeTwoLists(list1, list2->next);
//            return list2;
//        }
//    }
//};





//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//        if (list1 == nullptr) return list2;
//        if (list2 == nullptr) return list1;
//        ListNode* newhead = new ListNode(), * prev = newhead, * cur1 = list1, * cur2 = list2;
//        while (cur1 && cur2)
//        {
//            if (cur1->val < cur2->val)
//            {
//                prev->next = cur1, prev = prev->next, cur1 = cur1->next;
//            }
//            else
//            {
//                prev->next = cur2, prev = prev->next, cur2 = cur2->next;
//            }
//        }
//        prev->next = cur1 ? cur1 : cur2;
//        prev = newhead->next;
//        delete newhead;
//        return prev;
//    }
//};




//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        if (head == nullptr || head->next == nullptr) return head;
//        ListNode* newhead = reverseList(head->next);
//        head->next->next = head;
//        head->next = nullptr;
//        return newhead;
//    }
//};




//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        ListNode* newhead = new ListNode(), * cur = head;
//        while (cur)
//        {
//            ListNode* tmp = cur->next;
//            cur->next = newhead->next;
//            newhead->next = cur;
//            cur = tmp;
//        }
//        cur = newhead->next;
//        delete newhead;
//        return cur;
//    }
//};





//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (head == nullptr || head->next == nullptr)
//            return head;
//        ListNode* nexthead = swapPairs(head->next->next);
//        ListNode* newhead = head->next;
//        newhead->next = head;
//        head->next = nexthead;
//        return newhead;
//    }
//};




//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (head == nullptr || head->next == nullptr) return head;
//        ListNode* newhead = new ListNode(), * prev = newhead, * cur = head;
//        while (cur && cur->next)
//        {
//            ListNode* tmp = cur->next->next;
//            prev->next = cur->next;
//            cur->next->next = cur;
//            prev = cur;
//            cur = tmp;
//        }
//        prev->next = cur;
//
//        prev = newhead->next;
//        delete newhead;
//        return prev;
//    }
//};




class Solution {
public:
    double myPow(double x, long long n) {
        return n < 0 ? 1.0 / dfs(x, -n) : dfs(x, n);
    }

    double dfs(double x, long long n)
    {
        if (n == 0)
            return 1.0;
        double tmp = dfs(x, n / 2);
        return n % 2 == 1 ? tmp * tmp * x : tmp * tmp;
    }
};